1. Field of the Invention
Embodiments of the present invention generally relate to an image processing system and, more particularly, to a method and apparatus for performing an in-painting process on an image using prioritized graph cut optimization.
2. Description of the Related Art
Conventional computer-based image processing systems utilize various computer-vision principles and techniques, such as patch (block)-based in-painting and exemplar-based in-painting processes, to restore and/or otherwise improve images. These images may be damaged or include missing portions. Accordingly, the image processing systems modify pixels to improve visual quality, restore damaged portions and replace any missing regions.
These processes, however, are iterative solutions that divide an image into a plurality of blocks (e.g., eight×eight pixels, sixteen×sixteen pixels and the like) and operate on a block-by-block basis to perform in-painting. Basically, the typical process in-paints individual blocks and not groups of blocks. In other words, such techniques do not efficiently and accurately identify the best labels for multiple blocks to be in-painted during a single iteration. Labels generally translate into one or more intensity values where each value represents an amount or strength of at least one color component as displayed in one or more pixels (i.e., a block of pixels). Instead, these techniques assign labels one block at a time. While a label may be optimal for a certain block, the label is not optimal for the multiple blocks. Accordingly, errors often result from performing the in-painting process on the block-by-block basis. Erroneous labels are used in subsequent iterations resulting in propagation of the errors throughout the entire in-painting process. As a result, typical in-painting processes operate very slowly and inefficiently.
In addition, these processes employ various optimization (i.e., minimization) techniques to solve an in-painting problem by finding the best labels. Such optimization techniques evaluate pixel information of an image and assign labels to whole blocks of pixels. Each label represents an approximate intensity value for each and every pixel within the block. Therefore, instead of examining an intensity value for each primary color component of each pixel, these optimization techniques process labels that represent multiple intensity values for an entire block of pixels. Unfortunately, there are numerous potential labels for the pixels in the image. Because of the large number of labels (intensity values), executing any of these optimization techniques requires significant processing power. For example, implementing a graph-cut minimization technique for an image having more than two labels (for non-binary labeling in a non-binary image) is very complex and NP-hard (non-deterministic polynomial-time hard).
Therefore, there exists a need for a method and apparatus to perform an in-painting process on an image using a prioritized graph cut optimization technique.